package com.lhcai.lc.category.slidingwindow;

import java.util.*;

/**
 * 438. 找到字符串中所有字母异位词
 *
 * @author liuhuaicai
 * @since 2024-10-14 21:56
 */
public class Lc438 {
    public static void main(String[] args) {
        Lc438 lc438 = new Lc438();
        System.out.println(lc438.findAnagrams("abab", "ab"));
    }

    public List<Integer> findAnagrams(String s, String p) {
        // 记录p中字母出现的次数
        int[] arr = new int[26];
        for (int i = 0; i < p.length(); i++) {
            arr[p.charAt(i) - 'a'] += 1;
        }
        List<Integer> res = new ArrayList<>();
        // 设置左右指针，右指针移动
        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            // s 中字符出现了，出现一次，自减一次
            arr[s.charAt(right) - 'a']--;
            // 小于零的时候，代表 窗口内  出现了p 之外 的多余字母
            while (arr[s.charAt(right) - 'a'] < 0) {
                // 左指针开始追赶，窗口变小，直到追赶到有指针对应的相同字符处
                arr[s.charAt(left) - 'a']++;
                left++;
            }
            // 符合条件
            if (right - left + 1 == p.length()) {
                res.add(left);
            }
        }
        return res;
    }
}